﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics.Contracts;

namespace DataStructure
{
    public class Nodes
    {
        public Nodes(int data)
        {
            Data = data;
        }

        public Nodes(int data, Nodes next)
        {
            Data = data;
            Next = next;
        }

        public Nodes( int [] datas)
        {
            if (datas.Length == 0)
                throw new ArgumentException();
            Data = datas[0];
            var current = this;
            for (int i = 1; i < datas.Length; i++)
            {
                var l = new Nodes(datas[i]);
                current.Next = l;
                current = l;
            }
        }
        public Nodes GetNode(int k)
        {
            int count = 0;
            Nodes current = this;
            while (current != null)
            {
                count++;
                if (count == k)
                    return current;
                current = current.Next;
            }

            return null;
        }

        public int GetLength()
        {
            int count = 0;
            Nodes current = this;
            while (current != null)
            {
                count++;
                current = current.Next;
            }
            return count;
        }

        public Nodes(Nodes l)
        {
            this.Data = l.Data;
            this.Next = l.Next;
        }
        public void Show()
        {
            Nodes current = this;
            while (current != null)
            {
                Console.Write(current.Data + " ");
                current = current.Next;
            }
            Console.WriteLine();
        }
        Nodes Next;
        public int Data { get; set; }

        /// <summary>
        /// the base index is 1
        /// </summary>
        /// <param name="list"></param>
        /// <param name="k"></param>
        public static void Reverse(Nodes list, int k)
        {
            int length = list.GetLength();
            int count = length - k * 2;

            Nodes start = list.GetNode(k);
            Nodes end = list.GetNode(length + 1 - k);
            if (count == 1)
            {
                return;
            }
            else if (count == 2)
            {
                var n = start.Next.Next;
                start.Next.Next = end;
                start.Next = n;
            }
            
            Nodes a = start.Next;
            Nodes b = a.Next;
            Nodes c = null;

            Nodes current;
            int currentCount = 0;
            while (++currentCount < count)
            {
                current = a;
                c = b.Next;
                b.Next = current;
                current = b;
                b = c;
            }
            start.Next.Next = end;
            if (a != null)
                start.Next = a;
            
        }
    }

    public class SqList<T>
    {
        T[] elems;
        private int length;
        public int Length { get { return length; } }
        public int Capacity { get { return elems.Length; } }
        public SqList()
        {
            elems = (T[])Array.CreateInstance(typeof(T), 16);
            length = 0;
        }

        public SqList(int capacity)
        {
            Contract.Requires(capacity >= 0);
            Contract.Ensures(length == 0, string.Format("the length is {0}", length));
            elems = (T[])Array.CreateInstance(typeof(T), capacity);
            length = 0;
            
        }
        public T this[int index]
        {
            get {
                
                return elems[index]; }
        }
        public void Insert(int pos, T e)
        {
            if (pos > Length)
            {
                throw new ArgumentException("");
            }

            if (Length == Capacity)
            {
                T[] temp = (T[])Array.CreateInstance(typeof(T), 2 * elems.Length);
                Array.Copy(elems, temp, Length);
                elems = temp;
            }
            int index = Length -1;
            while (index >= pos)
            {
                elems[index + 1] = elems[index];
                index--;
            }

            elems[pos] = e;
            ++length;
        }
        public void Remove(int index, T e)
        {

        }

        public static void Union<T>(SqList<T> a, SqList<T> b)
        {
            // error handle
            for (int i = 0; i < b.Length; i++)
            {
                if(!a.elems.Contains(b[i]))
                {
                    a.Insert(a.Length, b[i]);
                }
            }
        }
        public static SqList<T> MergeList<T>(SqList<T> a, SqList<T> b)
        {
            SqList<T> result = new SqList<T>();

            return result;
        }
    }
}
